package lc_600_不含连续1的非负整数;

public class Solution {

    private int n;

    private int f(int index, int limit, int last, int flag, Integer[][][] dp) {
        if (index == -1) {
            return flag;
        }
        if (limit == 0 && dp[index][last][flag] != null) {
            return dp[index][last][flag];
        }
        int t = n >> index & 1;
        int r = limit == 1 ? t : 1;
        int ans = 0;
        for (int i = 0; i <= r; i++) {
            ans += f(index - 1, limit == 1 && i == t ? 1 : 0, i, flag == 1 || last == 1 && i == 1 ? 1 : 0, dp);
        }
        if (limit == 0)
            dp[index][last][flag] = ans;
        return ans;
    }

    public int findIntegers(int n) {
        this.n = n;
        int size = 32 - Integer.numberOfLeadingZeros(n);
        Integer[][][] dp = new Integer[size][2][2];
        return n + 1 - f(size - 1, 1, 0, 0, dp);
    }
}